{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Total Appeal of A String"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #hash-table #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #哈希表 #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: appealSum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #字符串的总引力"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>字符串的 <strong>引力</strong> 定义为：字符串中 <strong>不同</strong> 字符的数量。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，<code>\"abbca\"</code> 的引力为 <code>3</code> ，因为其中有 <code>3</code> 个不同字符 <code>'a'</code>、<code>'b'</code> 和 <code>'c'</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>给你一个字符串 <code>s</code> ，返回 <strong>其所有子字符串的总引力</strong> <strong>。</strong></p>\n",
    "\n",
    "<p><strong>子字符串</strong> 定义为：字符串中的一个连续字符序列。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>s = \"abbca\"\n",
    "<strong>输出：</strong>28\n",
    "<strong>解释：</strong>\"abbca\" 的子字符串有：\n",
    "- 长度为 1 的子字符串：\"a\"、\"b\"、\"b\"、\"c\"、\"a\" 的引力分别为 1、1、1、1、1，总和为 5 。\n",
    "- 长度为 2 的子字符串：\"ab\"、\"bb\"、\"bc\"、\"ca\" 的引力分别为 2、1、2、2 ，总和为 7 。\n",
    "- 长度为 3 的子字符串：\"abb\"、\"bbc\"、\"bca\" 的引力分别为 2、2、3 ，总和为 7 。\n",
    "- 长度为 4 的子字符串：\"abbc\"、\"bbca\" 的引力分别为 3、3 ，总和为 6 。\n",
    "- 长度为 5 的子字符串：\"abbca\" 的引力为 3 ，总和为 3 。\n",
    "引力总和为 5 + 7 + 7 + 6 + 3 = 28 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>s = \"code\"\n",
    "<strong>输出：</strong>20\n",
    "<strong>解释：</strong>\"code\" 的子字符串有：\n",
    "- 长度为 1 的子字符串：\"c\"、\"o\"、\"d\"、\"e\" 的引力分别为 1、1、1、1 ，总和为 4 。\n",
    "- 长度为 2 的子字符串：\"co\"、\"od\"、\"de\" 的引力分别为 2、2、2 ，总和为 6 。\n",
    "- 长度为 3 的子字符串：\"cod\"、\"ode\" 的引力分别为 3、3 ，总和为 6 。\n",
    "- 长度为 4 的子字符串：\"code\" 的引力为 4 ，总和为 4 。\n",
    "引力总和为 4 + 6 + 6 + 4 = 20 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>s</code> 由小写英文字母组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [total-appeal-of-a-string](https://leetcode.cn/problems/total-appeal-of-a-string/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [total-appeal-of-a-string](https://leetcode.cn/problems/total-appeal-of-a-string/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"abbca\"', '\"code\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appealSum(self, s: str) -> int:\n",
    "        nums, n = [-1] * 27, len(s)\n",
    "        print(ord('a'))\n",
    "        res = 0\n",
    "        for i, c in enumerate(s):\n",
    "            res += (i - nums[ord(c) - ord('a')]) * (n - i)\n",
    "            nums[ord(c) - ord('a')] = i\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appealSum(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        ans=0\n",
    "        pre=0\n",
    "        \n",
    "        lastindex=[-1]*26\n",
    "        \n",
    "        for i in range(n):\n",
    "            this=pre+i-lastindex[ord(s[i])-ord('a')]\n",
    "            ans+=this\n",
    "            pre=this\n",
    "            \n",
    "            \n",
    "            lastindex[ord(s[i])-ord('a')]=i\n",
    "        \n",
    "        \n",
    "        \n",
    "        return ans\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appealSum(self, s: str) -> int:\n",
    "        ans, Sum, pre = 0, 0, {}\n",
    "        for i,c in enumerate(s):\n",
    "            Sum += i-pre.get(c, -1)\n",
    "            ans += Sum\n",
    "            pre[c] = i\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appealSum(self, s: str) -> int:\n",
    "        ans = dt = 0\n",
    "        dct = {}\n",
    "        for i, c in enumerate(s):\n",
    "            dt += i - dct.get(c, -1)\n",
    "            ans += dt\n",
    "            dct[c] = i\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appealSum(self, s: str) -> int:\n",
    "        result = 0\n",
    "        n = len(s)\n",
    "        pre = [-1]*26\n",
    "        for i in range(n):\n",
    "            te = ord(s[i])-ord('a')\n",
    "            # if pre[te]==-1:\n",
    "            #     result += (n-i)*(i+1)\n",
    "            # else:\n",
    "            result += (n-i)*(i-pre[te])\n",
    "            pre[te] = i\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appealSum(self, s: str) -> int:\n",
    "        result = 0\n",
    "        pre = [-1]*26\n",
    "        for i in range(len(s)):\n",
    "            result += (len(s)-i)*(i-pre[ord(s[i])-ord('a')])\n",
    "            pre[ord(s[i])-ord('a')] = i\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appealSum(self, s: str) -> int:\n",
    "        result = 0\n",
    "        n = len(s)\n",
    "        pre = [-1]*26\n",
    "        for i in range(n):\n",
    "            result += (n-i)*(i-pre[ord(s[i])-ord('a')])\n",
    "            pre[ord(s[i])-ord('a')] = i\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "class Solution:\n",
    "    def appealSum2(self,s,tag):\n",
    "        if tag<=1:\n",
    "            return tag\n",
    "        temp=len(set(s))\n",
    "        if temp==tag:\n",
    "            return int((1+tag)*tag/2)\n",
    "        if temp==1:\n",
    "            return tag\n",
    "        return temp+self.appealSum2(s[:-1],tag-1)\n",
    "    def appealSum(self, s: str) -> int:\n",
    "        sumTag=0\n",
    "        T=len(s)\n",
    "        for i in range(T):\n",
    "            sumTag= sumTag + self.appealSum2(s[i:],T-i)\n",
    "        return sumTag\n",
    "'''\n",
    "class Solution:\n",
    "    def appealSum(self, s: str) -> int:\n",
    "        ans, sum_g, last = 0, 0, {}\n",
    "        for i, c in enumerate(s):\n",
    "            sum_g += i - last.get(c, -1)  # 将提示 2-2 中的两种情况合并成一个公式\n",
    "            ans += sum_g\n",
    "            last[c] = i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appealSum(self, s: str) -> int:\n",
    "        last_occur = defaultdict(lambda: -1)\n",
    "        last_occur[s[0]] = 0\n",
    "\n",
    "        sm_gravity, curr_gravity = 1, 1\n",
    "        for i in range(1, len(s)):\n",
    "            curr_gravity += i - last_occur[s[i]]\n",
    "            sm_gravity += curr_gravity\n",
    "            last_occur[s[i]] = i\n",
    "\n",
    "        return sm_gravity\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appealSum(self, s: str) -> int:\n",
    "        nearest=[-1 for _ in range(len(s))]\n",
    "        repeat_d=dict()\n",
    "        for i in range(len(s)-1,-1,-1):\n",
    "            if s[i] in repeat_d:\n",
    "                nearest[i]=repeat_d[s[i]]-i\n",
    "            repeat_d[s[i]]=i\n",
    "        print(nearest)\n",
    "        last_res=0\n",
    "        d = dict()\n",
    "        final_res=0\n",
    "        for j in range(len(s)):\n",
    "            if s[j] in d:\n",
    "                d[s[j]] = d[s[j]] + 1\n",
    "            else:\n",
    "                d[s[j]] = 1\n",
    "            last_res += len(d)\n",
    "        final_res+=last_res\n",
    "        last_length=len(s)\n",
    "        for i in range(1,len(s)):\n",
    "            if nearest[i-1]==-1:\n",
    "\n",
    "                last_res=last_res-last_length\n",
    "            else:\n",
    "                last_res=last_res-nearest[i-1]\n",
    "            last_length -= 1\n",
    "            final_res+=last_res\n",
    "            #print(last_res)\n",
    "        return final_res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appealSum(self, s: str) -> int:\n",
    "        d={}\n",
    "        n=len(s)\n",
    "        db=[0 for i in range(n)]\n",
    "        ans=0\n",
    "        num=0\n",
    "        for i,t in enumerate(s):\n",
    "            num+=i-d.get(t,-1)\n",
    "            ans+=num\n",
    "            d[t]=i\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appealSum(self, s: str) -> int:\n",
    "        @cache\n",
    "        def getAn0(k):\n",
    "            return k * (k+1) // 2\n",
    "        \n",
    "        def getAns(c):\n",
    "            an = an0\n",
    "            fs = []\n",
    "            for ch in s:\n",
    "                fs.append(ch == c)\n",
    "                \n",
    "            startI = None\n",
    "            for i, f in enumerate(fs):\n",
    "                if f:\n",
    "                    if startI != None:\n",
    "                        an -= getAn0(i-startI)\n",
    "                    startI = None    \n",
    "                else:\n",
    "                    if startI == None:\n",
    "                        startI = i\n",
    "            if startI != None:\n",
    "                an -= getAn0(n-startI)\n",
    "            return an\n",
    "        \n",
    "        n = len(s)\n",
    "        an0 = getAn0(n)\n",
    "        ans = 0\n",
    "        for c in \"abcdefghijklmnopqrstuvwxyz\":\n",
    "            ans += getAns(c)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appealSum(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        rec=[-1]*n\n",
    "        last = {}\n",
    "        ans = 0\n",
    "        last_res = 0\n",
    "        for i,v in enumerate(s):\n",
    "            if v in last:\n",
    "                last_res+=i-last[v]      \n",
    "                ans += last_res\n",
    "            else:\n",
    "                last_res += i+1\n",
    "                ans += last_res\n",
    "\n",
    "            last[v] = i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appealSum(self, s: str) -> int:\n",
    "        left, book = [0] * (n := len(s)), [-1] * 26\n",
    "        for i, ch in enumerate(s):\n",
    "            left[i] = i - book[idx := ord(ch) - 97]\n",
    "            book[idx] = i\n",
    "        return sum(left[i] * (n - i) for i in range(n))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class FenwickTree:\n",
    "    def __init__(self, n):\n",
    "        self.arr = [0 for _ in range(n + 1)]\n",
    "        self.arr2 = [0 for _ in range(n + 1)]\n",
    "\n",
    "    def update(self, idx: int, delta: int):\n",
    "        n = len(self.arr)\n",
    "        pos = idx\n",
    "        while idx < n:\n",
    "            self.arr[idx] += delta\n",
    "            self.arr2[idx] += delta * pos\n",
    "            idx += self.lowbit(idx)\n",
    "\n",
    "    def range_update(self, l: int, r: int, delta: int):\n",
    "        self.update(l, delta)\n",
    "        self.update(r + 1, -delta)\n",
    "\n",
    "    def query(self, idx: int) -> int:\n",
    "        ans = 0\n",
    "        pos = idx\n",
    "        while idx:\n",
    "            ans += (self.arr[idx] * (pos + 1) - self.arr2[idx])\n",
    "            idx -= self.lowbit(idx)\n",
    "        return ans\n",
    "\n",
    "    def range_query(self, l: int, r: int) -> int:\n",
    "        return self.query(r) - self.query(l - 1)\n",
    "\n",
    "    def lowbit(self, x: int) -> int:\n",
    "        return x & -x\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def appealSum(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        bit = FenwickTree(n)\n",
    "        indexs = collections.defaultdict(lambda:-1)\n",
    "        ans = 0\n",
    "        for i, ch in enumerate(s):\n",
    "            bit.range_update(indexs[ch] + 2, i + 1, 1)\n",
    "            indexs[ch] = i\n",
    "            ans += bit.range_query(1, i + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appealSum(self, s: str) -> int:\n",
    "        d = {}\n",
    "        dp = [0 for i in range(len(s) + 1)]\n",
    "        for i, x in enumerate(s):\n",
    "            dp[i + 1] = dp[i] + i - d.get(x, -1) # 当不存在 j 时, j 为-1\n",
    "            d[x] = i\n",
    "        return sum(dp)\n",
    "\n",
    "        # ans, sum_, d = 0, 0, {}\n",
    "        # for i, c in enumerate(s):            \n",
    "        #     sum_ += i - d.get(c, -1)\n",
    "        #     ans += sum_\n",
    "        #     d[c] = i\n",
    "        # return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appealSum(self, s: str) -> int:\n",
    "        from collections import deque\n",
    "        m = defaultdict(deque)\n",
    "        si = 0\n",
    "        res = 0 \n",
    "        n = len(s)\n",
    "        \n",
    "        \n",
    "        for i in range(n):\n",
    "            m[s[i]].append(i)\n",
    "            si += len(m)\n",
    "        \n",
    "        for i in range(n):\n",
    "            res += si\n",
    "            si -= 1\n",
    "            \n",
    "            m[s[i]].popleft()\n",
    "            if len(m[s[i]]) == 0:\n",
    "                del m[s[i]]\n",
    "                si -= n - (i+1)\n",
    "            else:\n",
    "                si -= m[s[i]][0] - (i+1)\n",
    "            \n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appealSum(self, s: str) -> int:\n",
    "        l = len(s)\n",
    "        d = dict()\n",
    "        dp = [0 for i in range(l+1)]\n",
    "        for i in range(l):\n",
    "            dp[i+1] = dp[i] + i - d.get(s[i], -1)\n",
    "            d[s[i]] = i\n",
    "        return sum(dp)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appealSum(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp = [1] * n\n",
    "        record = {}\n",
    "        record[s[0]] = 0\n",
    "        for i in range(1, n):\n",
    "            dp[i] = dp[i - 1] + (i - record.get(s[i], -1))\n",
    "            record[s[i]] = i \n",
    "        return sum(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appealSum(self, s: str) -> int:\n",
    "        d, dp = {}, [0]*(len(s)+1)\n",
    "        for i, c in enumerate(s):\n",
    "            dp[i] = dp[i-1] + i - d.get(c, -1)\n",
    "            d[c] = i\n",
    "        return sum(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appealSum(self, s: str) -> int:\n",
    "        dp, latestIdx = [0] * len(s), {s[0]: 0}\n",
    "        dp[0] = 1\n",
    "        for i in range(1, len(s)):\n",
    "            last = latestIdx.get(s[i],-1)\n",
    "            dp[i] = dp[i - 1] + i - last\n",
    "            latestIdx[s[i]] = i\n",
    "        return sum(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appealSum(self, s: str) -> int:\n",
    "        d = {}\n",
    "        dp = [0]*(len(s)+1)\n",
    "        for i, c in enumerate(s):\n",
    "            dp[i] = dp[i-1] + i - d.get(c, -1)\n",
    "            d[c] = i\n",
    "        return sum(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 问题转化为每个字符对答案的贡献\n",
    "# 找到每个字符左边第一个相同的位置l\n",
    "# 如果一个字串包含多个相同的字符, 规定第一个字符对答案做出贡献\n",
    "# 那么它的总贡献为(i - l[i]) * (n - i)\n",
    "class Solution:\n",
    "    def appealSum(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        l = [0] * n\n",
    "        last = [-1] * 26\n",
    "        for i in range(n):\n",
    "            l[i] = last[ord(s[i]) - ord('a')]\n",
    "            last[ord(s[i]) - ord('a')] = i\n",
    "\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            res += (i - l[i]) * (n - i)\n",
    "        return res     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appealSum(self, s: str) -> int:\n",
    "        # dp[i] [j, i] 0 <= j <= i\n",
    "        # s[i] 是否包含于[j, i - 1]\n",
    "        n = len(s)\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        \n",
    "        dp = [0] * n\n",
    "        pre = dict()\n",
    "        for i, c in enumerate(s):\n",
    "            if i == 0:\n",
    "                dp[i] = 1\n",
    "            else:\n",
    "                dp[i] = dp[i - 1] + 1 + (i - 1 - pre.get(c, -1))\n",
    "            \n",
    "            pre[c] = i\n",
    "        \n",
    "        return sum(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appealSum(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        dic={}\n",
    "        dp=[0]*n\n",
    "        for i in range (0,n):\n",
    "            if i==0:\n",
    "                dp[i]=1\n",
    "                dic[s[i]]=i\n",
    "            else:\n",
    "                if s[i] not in dic:\n",
    "                    dic[s[i]]=i\n",
    "                    dp[i]=dp[i-1]+i+1\n",
    "                else:\n",
    "                    dp[i]=dp[i-1]+i-dic[s[i]]\n",
    "                    dic[s[i]]=i\n",
    "        return sum(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appealSum(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp = [1] * n\n",
    "        pos = {x: -1 for x in string.ascii_lowercase}\n",
    "        pos[s[0]] = 0\n",
    "        for i, x in enumerate(s[1:], 1):\n",
    "            if s[i] == s[i - 1]:\n",
    "                dp[i] = dp[i - 1] + 1\n",
    "            else:\n",
    "                j = pos[x]\n",
    "                if j == -1:\n",
    "                    dp[i] = dp[i - 1] + i + 1\n",
    "                else:\n",
    "                    # print(i, j, dp[i - 1])\n",
    "                    dp[i] = dp[i - 1] + (i - j)\n",
    "            pos[x] = i\n",
    "        # print(pos)\n",
    "        # print(dp)\n",
    "        return sum(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appealSum(self, s: str) -> int:\n",
    "        #贡献度计算,每一个字母会在pre+1 到 next -1的位置做贡献呢!\n",
    "        n=len(s)\n",
    "        pre=[-1]*n\n",
    "        #nxt=[n]*n\n",
    "        last=[-1]*26\n",
    "        res=0\n",
    "        for i in range(n):\n",
    "            cur = ord(s[i])-ord('a')\n",
    "            pre[i]=last[cur]\n",
    "            #if last[cur]!=-1:\n",
    "            #    nxt[last[cur]]=i\n",
    "            last[cur]=i\n",
    "        for i in range(n):\n",
    "            left = i - pre[i]\n",
    "            right = n-i\n",
    "            res+=(left*right)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appealSum(self, s: str) -> int:\n",
    "        dct, repcnt, ans = defaultdict(list), 0, 0\n",
    "        for i, c in enumerate(s):\n",
    "            if c in dct:\n",
    "                repcnt += dct[c][-1]\n",
    "            dct[c].append(i + 1)\n",
    "            ans += ((i + 1) * (i + 2) >> 1) - repcnt\n",
    "            #print(s, dct, repcnt, ans)\n",
    "        return ans\n",
    "            \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appealSum(self, s: str) -> int:\n",
    "        d=dict() \n",
    "        for i,v in enumerate(s): \n",
    "            if v in d: d[v].append(i)    \n",
    "            else: d[v]=[i]  \n",
    "        ret=0\n",
    "        n=len(s)      \n",
    "        for key in d: \n",
    "            lst=d[key]\n",
    "            last=-1\n",
    "            for  i in lst: \n",
    "                ret+=(i-last)*(n-i)    \n",
    "                last=i    \n",
    "        return ret \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appealSum(self, s: str) -> int:\n",
    "        index = defaultdict(list)\n",
    "        for i, c in enumerate(s):\n",
    "            index[c].append(i)\n",
    "        ans = 0\n",
    "        for il in index.values():\n",
    "            il.append(len(s))\n",
    "            for i in range(len(il)-1):\n",
    "                ans += (il[i] +1) * (il[i+1] - il[i])\n",
    "                pre = il[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appealSum(self, s: str) -> int:\n",
    "        dic=collections.defaultdict(list)\n",
    "        n=len(s)\n",
    "        for i in range(26):\n",
    "            dic[i].append(-1)\n",
    "        for i,val in enumerate(s):\n",
    "            dic[ord(val)-ord('a')].append(i)\n",
    "        for i in range(26):\n",
    "            dic[i].append(n)\n",
    "        \n",
    "        #print(dic)\n",
    "        \n",
    "        ans=0\n",
    "        for i in range(26):\n",
    "            for j in range(1,len(dic[i])-1):\n",
    "                left=dic[i][j-1]\n",
    "                mid=dic[i][j]\n",
    "                right=n\n",
    "                ans+=(mid-left)*(right-mid)\n",
    "        return ans \n",
    "        \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # dp\n",
    "    # https://leetcode.cn/problems/total-appeal-of-a-string/solution/python-ha-xi-dp-by-qin-qi-shu-hua-2-4hfz/\n",
    "    def appealSum(self, s: str) -> int:\n",
    "        l = len(s)\n",
    "        dp = [0 for i in range(l + 1)]\n",
    "        d = {}\n",
    "        for i, n in enumerate(s):\n",
    "            dp[i + 1] = dp[i] + i - d.get(n, -1) #当不存在j时,j为-1\n",
    "            d[n] = i\n",
    "\n",
    "        return sum(dp)\n",
    "\n",
    "\n",
    "\n",
    "    # https://leetcode.cn/problems/total-appeal-of-a-string/solution/by-endlesscheng-g405/\n",
    "    def appealSum2(self, s: str) -> int:\n",
    "        ans, sum_g, last = 0, 0, {}\n",
    "        for i, c in enumerate(s):\n",
    "            sum_g += i - last.get(c, -1)  # 将提示 2-2 中的两种情况合并成一个公式\n",
    "            ans += sum_g\n",
    "            last[c] = i\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appealSum(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        f, last = [1] + [0] * (n - 1), {s[0]: 0}\n",
    "        for i in range(1, n):\n",
    "            f[i] = f[i - 1] + (i - last.get(s[i], -1))\n",
    "            last[s[i]] = i\n",
    "        return sum(f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appealSum(self, s: str) -> int:\n",
    "        s = list(s)\n",
    "        sub_str_len = [0 for i in range(len(s)+1)]\n",
    "        last = {}\n",
    "        for i in range(0, len(s)):\n",
    "            sub_str_len[i+1] = sub_str_len[i] + i - last.get(s[i], -1)\n",
    "            last[s[i]] = i\n",
    "        return sum(sub_str_len)\n",
    "\n",
    "# class Solution:\n",
    "#     def appealSum(self, s: str) -> int:\n",
    "#         result = 0\n",
    "#         s = list(s)\n",
    "#         for i in range(0, len(s)):\n",
    "#             rest = s[i:]\n",
    "#             # print(i, ' ', rest)\n",
    "#             for j in range(0, len(rest)):\n",
    "#                 cur_str = set(rest[0 : j + 1])\n",
    "#                 # print(j, ' ', rest, ' ' , cur_str, ' ' , len(cur_str))\n",
    "#                 result += len(cur_str)\n",
    "#         return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def appealSum(self, s: str) -> int:\n",
    "\n",
    "        l = len(s)\n",
    "\n",
    "        dp = [0 for i in range(l + 1)]\n",
    "\n",
    "        d = {}\n",
    "\n",
    "        for i, n in enumerate(s):\n",
    "\n",
    "            dp[i + 1] = dp[i] + i - d.get(n, -1) #当不存在j时,j为-1\n",
    "\n",
    "            d[n] = i\n",
    "\n",
    "        return sum(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appealSum(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        d = defaultdict(list)\n",
    "        for i, ch in enumerate(s):\n",
    "            d[ch].append(i)\n",
    "        ans = 0\n",
    "        for v in d.values():\n",
    "            tmp = v + [n]\n",
    "            for x, y in pairwise(tmp):\n",
    "                ans += (y - x) * (x + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import *\n",
    "class Solution:\n",
    "    def appealSum(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        dp=[0]*(n+1)\n",
    "        d=[-1]*26\n",
    "        for i in range(n):\n",
    "            c=ord(s[i])-ord('a')\n",
    "            dp[i+1]=dp[i]+i-d[c]\n",
    "            d[c]=i\n",
    "        return sum(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appealSum(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp = [0 for _ in range(n)]\n",
    "\n",
    "        dp[0] = 1\n",
    "        dic = dict()\n",
    "        dic[s[0]] = 0\n",
    "\n",
    "        for i in range(1,n):\n",
    "            if s[i] in dic:\n",
    "                dp[i] = dp[i-1] + i - dic[s[i]]\n",
    "                dic[s[i]] = i\n",
    "            else:\n",
    "                dp[i] = dp[i-1] + i + 1\n",
    "                dic[s[i]] = i\n",
    "        res = sum(dp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appealSum(self, s: str) -> int:\n",
    "        dp = [0 for _ in range(len(s))]\n",
    "        last = {}\n",
    "        for i in range(len(s)):\n",
    "            if i == 0:\n",
    "                dp[i] = 1\n",
    "            else:\n",
    "                index = last.get(s[i],-1)\n",
    "                a = i - index\n",
    "                dp[i] = dp[i-1]+a\n",
    "            last[s[i]] = i\n",
    "        return sum(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appealSum(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        pre = [-1]*26\n",
    "        res = [0]*n\n",
    "        res[0] = 1\n",
    "        pre[ord(s[0])-ord('a')] = 0\n",
    "        for i in range(1,n):\n",
    "            res[i] = res[i-1]\n",
    "            res[i] += i-pre[ord(s[i])-ord('a')]\n",
    "            pre[ord(s[i])-ord('a')] = i\n",
    "        return sum(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appealSum(self, s: str) -> int:               \n",
    "        # a     1 = 1       a没有出现在'',  0 + 0 + 1   (pre_ans+i+1) 如果没出现过， (pre_ans+i-上一次出现的位置+1)如果出现过了\n",
    "        # ab    2+1 = 3     b没有出现在a,   1 + 1 + 1\n",
    "        # abb   2+1+1 = 4   b出现在ab     , 3 + 0 + 1\n",
    "        # abbc  3+2+2+1= 8  c没有出现在abb, 4 + 3 + 1\n",
    "        # abbca 3+3+3+2+1 = 12 a出现在abbca 8 + i-上一次a出现的位置 + 1\n",
    "        n = len(s)\n",
    "        d = defaultdict(int)\n",
    "        f = [0] * (n+1)\n",
    "        for i, c in enumerate(s):\n",
    "            if c in d:\n",
    "                f[i+1] = f[i] + i - d[c]\n",
    "            else:\n",
    "                f[i+1] = f[i] + i + 1\n",
    "            d[c] = i # 位置需要更新\n",
    "        # print(f)\n",
    "        return sum(f)\n",
    "\n",
    "        # ktttt\n",
    "        # k             1\n",
    "        # kt          1+2\n",
    "        # ktt       1+1+2\n",
    "        # kttt    1+1+1+2\n",
    "        # ktttt 1+1+1+1+2\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appealSum(self, s: str) -> int:\n",
    "        if s=='':\n",
    "            return 0\n",
    "        n=len(s)\n",
    "        dt=dict()\n",
    "        dt[s[0]]=0\n",
    "        dp=[0]*n\n",
    "        dp[0]=1\n",
    "        for i in range(1,n):\n",
    "            c=s[i]\n",
    "            if c not in dt:\n",
    "                dp[i]=dp[i-1]+(i+1)\n",
    "            else:\n",
    "                dp[i]=dp[i-1]+i-dt[c]\n",
    "            dt[c]=i \n",
    "        # print(dp)\n",
    "        return sum(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @lru_cache(None)\n",
    "    def appealSum(self, s: str) -> int:\n",
    "        s = list(s)\n",
    "        n = len(s)\n",
    "        if n < 2:\n",
    "            return n\n",
    "        chars = collections.defaultdict()\n",
    "        chars[s[n - 1]] = n - 1\n",
    "        dp = [0] * n \n",
    "        dp[n - 1] = 1\n",
    "        for i in range(n - 2, - 1, -1):\n",
    "            same_index = n\n",
    "            if s[i] in chars:\n",
    "                same_index = chars[s[i]]\n",
    "            \n",
    "            chars[s[i]] = i\n",
    "           \n",
    "            dp[i] = 1 + dp[i + 1] + same_index - i - 1\n",
    "        return sum(dp)\n",
    "\n",
    "        # cnt = 1\n",
    "        # curr_appeal = 1\n",
    "        # chs = {s[0]}\n",
    "        # for i in range(1, n):\n",
    "        #     if curr_appeal == 26:\n",
    "        #         cnt += 26 * (n - i)\n",
    "        #         break\n",
    "        #     if s[i] not in chs:\n",
    "        #         curr_appeal += 1\n",
    "        #         chs.add(s[i])\n",
    "        #     cnt += curr_appeal\n",
    "        # return cnt + self.appealSum(''.join(s[1:]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @lru_cache(None)\n",
    "    def appealSum(self, s: str) -> int:\n",
    "        s = list(s)\n",
    "        n = len(s)\n",
    "        if n < 2:\n",
    "            return n\n",
    "        # chars = collections.defaultdict(list)\n",
    "        # for i, ch in enumerate():\n",
    "\n",
    "\n",
    "        dp = [0] * n \n",
    "        dp[n - 1] = 1\n",
    "        for i in range(n - 2, - 1, -1):\n",
    "            same_index = n\n",
    "            for j in range(i + 1, n):\n",
    "                if s[i] == s[j]:\n",
    "                    same_index = j\n",
    "                    break\n",
    "           \n",
    "            dp[i] = 1 + dp[i + 1] + same_index - i - 1\n",
    "        return sum(dp)\n",
    "\n",
    "        # cnt = 1\n",
    "        # curr_appeal = 1\n",
    "        # chs = {s[0]}\n",
    "        # for i in range(1, n):\n",
    "        #     if curr_appeal == 26:\n",
    "        #         cnt += 26 * (n - i)\n",
    "        #         break\n",
    "        #     if s[i] not in chs:\n",
    "        #         curr_appeal += 1\n",
    "        #         chs.add(s[i])\n",
    "        #     cnt += curr_appeal\n",
    "        # return cnt + self.appealSum(''.join(s[1:]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appealSum(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        pos = defaultdict(list)\n",
    "        for i,letter in enumerate(s):\n",
    "            pos[letter].append(i)\n",
    "        res = n+(len(pos)*n*(n-1))//2\n",
    "        for letter, l in pos.items():\n",
    "            if l[0]>=2:\n",
    "                res -= (l[0]*(l[0]-1))//2\n",
    "            if l[-1]<=n-3:\n",
    "                res -= ((n-1-l[-1])*(n-2-l[-1]))//2\n",
    "            m = len(l)\n",
    "            if m>=2:\n",
    "                for j in range(1,m):\n",
    "                    if l[j]-l[j-1]>=3:\n",
    "                        res -= ((l[j]-l[j-1]-1)*(l[j]-l[j-1]-2))//2\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appealSum(self, s: str) -> int:\n",
    "        d = defaultdict(list)\n",
    "        for i,x in enumerate(s):\n",
    "            d[x].append(i)\n",
    "        n = len(s)\n",
    "        ans = 0\n",
    "        for k,a in d.items():\n",
    "            ans += (a[0] + 1)*(n - a[0])\n",
    "            for i in range(1,len(a)):\n",
    "                ans += (a[i] - a[i - 1])*(n - a[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appealSum(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        countByAlpha = {i: [] for i in 'abcdefghijklmmnopqrstuvwxyz'}\n",
    "        for i, char in enumerate(s):\n",
    "            countByAlpha[char].append(i)\n",
    "        res = 0\n",
    "        for letter in countByAlpha:\n",
    "            index = countByAlpha[letter]\n",
    "            if index:\n",
    "                res += (n + 1) * n // 2\n",
    "                \n",
    "                gap = [index[0]]\n",
    "                i = 0\n",
    "                for i in range(1, len(index)):\n",
    "                    gap.append(index[i] - index[i - 1] - 1)\n",
    "                gap.append(n - index[i] - 1)\n",
    "\n",
    "                for i in range(len(gap)):\n",
    "                    res -= (gap[i] + 1) * gap[i] // 2  \n",
    "\n",
    "        return res\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appealSum(self, s: str) -> int:\n",
    "        l = len(s)\n",
    "        dp = [0 for i in range(l + 1)]\n",
    "        d = {}\n",
    "        for i, n in enumerate(s):\n",
    "            # print(f\"i: {i} dp: {dp}\")\n",
    "            dp[i + 1] = dp[i] + i - d.get(n, -1) #当不存在j时,j为-1\n",
    "            d[n] = i\n",
    "        print(dp)\n",
    "        print(d)\n",
    "        return sum(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_right as br,bisect_left as bl\n",
    "class Solution:\n",
    "    def appealSum(self, s: str) -> int:\n",
    "        chars = defaultdict(list)\n",
    "        length = len(s)\n",
    "        appeal_index = []\n",
    "        for i,char in enumerate(s):\n",
    "            chars[char].append(i)\n",
    "        \n",
    "        ans = 0\n",
    "        last = 0\n",
    "        for i,char in enumerate(s):\n",
    "            if i == 0:\n",
    "                appeal_index.append(len(chars.keys()))\n",
    "            else:\n",
    "                has_char = 0 if br(chars[s[i - 1]],i - 1) < len(chars[s[i - 1]]) else 1\n",
    "                appeal_index.append(appeal_index[-1] - has_char)\n",
    "        \n",
    "        ans = sum(appeal_index)\n",
    "        last = ans\n",
    "        # print(last)\n",
    "        # print(ans)\n",
    "        for i,char in enumerate(s[::-1]):\n",
    "            remove_idx = bl(chars[char], length - i - 1)\n",
    "            if remove_idx == 0:\n",
    "                last -= (length - i)\n",
    "            else:\n",
    "                last -= (length - i - 1 - chars[char][remove_idx - 1])\n",
    "            ans += last\n",
    "            # print(last)\n",
    "            # print(ans)\n",
    "        \n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appealSum(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        que = defaultdict(list)\n",
    "        for i, j in enumerate(s):\n",
    "            que[j].append(i)\n",
    "        ans = 0\n",
    "        for k, v in que.items():\n",
    "            pre = -1\n",
    "            for a in v:\n",
    "                ans += (n - a) * (a - pre)\n",
    "                pre = a \n",
    "        return ans "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
